﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class Solution207
    {
        int[] study;
        bool haveRing;
        public bool CanFinish(int numCourses, int[][] prerequisites)
        {

            IList<IList<int>> courseEdge = new List<IList<int>>();//存放当前课程的所以前置课程
            for (int i = 0; i < numCourses; i++)
            {

                courseEdge.Add(new List<int>());

            }


            for (int i = 0; i < prerequisites.Length; i++)
            {
                int pre = prerequisites[i][1];
                int cur = prerequisites[i][0];

                courseEdge[pre].Add(cur);
            }

           study = new int[numCourses];

           

           
            for (int i = 0; i < numCourses; i++)
            {

                if(study[i]==0)//可能是不连通的两个图，
                {
                    DFS(courseEdge, i);
                }

            }
            if (haveRing)
            {
                return false;
            }

            return true ;




        }
        public void DFS(IList<IList<int>> courseEdge,int curCourse)//遍历图，深度遍历
        {

           
            IList<int> curCourseList = courseEdge[curCourse];
            //遍历当前点的所有临边
            for (int i = 0; i < curCourseList.Count; i++)
            {
                int nextCourse = curCourseList[i];
                if (study[nextCourse]==1)//正在学习，有环
                {

                    haveRing=true;
                    return;

                }
                else if (study[nextCourse] == 0)//没有学习，学习
                {
                    DFS(courseEdge, nextCourse);
                }

              

            }
            //临边都学习过了
            study[curCourse] = 2;//学习完毕



        }
    
    
    
    
    }

    //广度优先遍历
    public class Solution207_2
    {
      
        public bool CanFinish(int numCourses, int[][] prerequisites)
        {

            IList<IList<int>> courseEdge = new List<IList<int>>();//存放当前课程的所有前置课程
            //存放入度
            int[] degree =new int[numCourses];
            for (int i = 0; i < numCourses; i++)
            {

                courseEdge.Add(new List<int>());

            }


            for (int i = 0; i < prerequisites.Length; i++)
            {
                int pre = prerequisites[i][1];
                int cur = prerequisites[i][0];

                courseEdge[pre].Add(cur);
                degree[cur]++ ;
            }

           

            int studyNum = 0;
            Stack<int> stack = new Stack<int>();//存放入度为0的
            

            for (int curCourse = 0; curCourse < numCourses; curCourse++)
            {

                if (degree[curCourse] == 0)//入度为0的设置为起点，如果有环，就找不到
                {
                    stack.Push(curCourse);
                  
                }

            }
           while (stack.Count > 0)
            {
                int curCourse = stack.Pop();
                //一门出度为0的，说明学完毕
                studyNum++;

                IList<int> curCourseList = courseEdge[curCourse];
                for (int i = 0; i < curCourseList.Count; i++)//入度减1
                {
                    int nextCourse = curCourseList[i];

                    degree[nextCourse]--;
                    if (degree[nextCourse] == 0)//入度为0的加入
                    {
                        stack.Push(nextCourse);

                    }




                }

            }

           if(studyNum == numCourses)
            {

                return true;
            }
            else
            {
                return false;
            }




        }
        




    }

}
